package oxing.util;

public final class HashMap<K, V> implements Map<K, V> {
	final static class Entry<K, V> {
		int hash;
		K key;
		V value;

		Entry<K, V> next;

		public Entry(int hash, K key, Entry<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.next = next;
		}
	}

	final static int DEFAULT_INITIAL_CAPACITY = 1 << 4;
	final static int MAXIMUM_CAPACITY = 1 << 30;
	final static Entry<?, ?>[] EMPTY_TABLE = {};
	@SuppressWarnings("unchecked")
	Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
	int threshold;
	int size;

	public HashMap(int capacity) {
		if (capacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + capacity);
		threshold = capacity >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
				: (capacity > 1) ? Integer.highestOneBit((capacity - 1) << 1) : 1;
	}

	@SuppressWarnings("unchecked")
	private Entry<K, V>[] inflateTable(int capacity) {
		threshold = (int) Math.min(capacity * 0.75f, MAXIMUM_CAPACITY + 1);
		return table = new Entry[capacity];
	}

	public V get(K key) {
		if (size == 0)
			return null;
		Entry<K, V> entry;
		int hash, index;
		index = null == key ? (hash = 0) : ((hash = hash(key)) & (table.length - 1));
		entry = getEntry(hash, key, index);
		return null == entry ? null : entry.value;
	}

	public boolean containsKey(K key) {
		if (size == 0)
			return false;
		Entry<K, V> entry;
		int hash, index;
		index = null == key ? (hash = 0) : ((hash = hash(key)) & (table.length - 1));
		entry = getEntry(hash, key, index);
		return null == entry;
	}

	public void put(K key, V value) {
		if (table == EMPTY_TABLE)
			inflateTable(threshold);
		Entry<K, V> entry;
		int hash, index;
		index = null == key ? (hash = 0) : ((hash = hash(key)) & (table.length - 1));
		entry = getEntry(hash, key, index);
		if (null == entry) {
			entry = addEntry(hash, key, index);
		}
		entry.value = value;
	}

	public V remove(K key) {
		if (size == 0)
			return null;
		Entry<K, V> entry;
		int hash, index;
		index = null == key ? (hash = 0) : ((hash = hash(key)) & (table.length - 1));
		entry = removeEntry(hash, key, index);
		return null == entry ? null : entry.value;
	}

	private Entry<K, V> getEntry(final int hash, final K key, final int index) {
		for (Entry<K, V> e = table[index]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
				return e;
		}
		return null;
	}

	private Entry<K, V> addEntry(final int hash, final K key, int index) {
		if ((size >= threshold) && (null != table[index])) {
			resize(table.length << 1);
			index = hash & (table.length - 1);
		}
		size++;
		return table[index] = new Entry<K, V>(hash, key, table[index]);
	}

	private Entry<K, V> removeEntry(final int hash, final K key, final int index) {
		if (table[index] == null)
			return null;
		Entry<K, V> e = table[index];
		Object k;
		if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
			size--;
			table[index] = e.next;
			return e;
		}
		for (Entry<K, V> e2 = e.next; e2 != null; e2 = (e = e2).next) {
			if (e2.hash == hash && ((k = e2.key) == key || (key != null && key.equals(k)))) {
				size--;
				e.next = e2.next;
				return e2;
			}
		}
		return null;
	}

	private void resize(int newCapacity) {
		Entry<K, V>[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry<K, V>[] newTable = inflateTable(newCapacity);
		Entry<K, V> entry, next;
		int index;
		for (int i = 0; i < oldCapacity; i++) {
			entry = oldTable[i];
			while (null != entry) {
				next = entry.next;
				index = entry.hash & (newCapacity - 1);
				entry.next = newTable[index];
				newTable[index] = entry;
				entry = next;
			}
		}
	}

	private int hash(Object k) {
		int h = k.hashCode();
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}
}